1. Technical Field
The present invention is directed to an apparatus and method for distribution of work on a doubly linked list among processing threads. More specifically, the present invention is directed to a mechanism for maintaining information regarding work to be done, and work assigned or completed, by one or more processing threads.
2. Description of Related Art
Linked lists are data management mechanisms which allow for the organization of a sequential set of data in noncontiguous storage locations. In a standard linked list each element of the list contains a pointer to the next element in the list. Thus, each element is linked to the next element in the list. In a doubly linked list, each element in the doubly linked list includes a first pointer that points to the next element in the doubly linked list and a second pointer that points to the previous element in the doubly linked list.
FIG. 1 is an example graphical depiction of a doubly linked list. As shown in FIG. 1, the doubly linked list 100 includes a list header 102 and a plurality of list elements 105. The list header 102 includes a list lock 110 that protects the contents of the list and a pointer 120 to the first element 105 in the list. The plurality of elements 105 in the linked list each include a pair of pointers 140 and 150 that point to the element 160 before the current element 130 and the element 170 after the current element in the linked list 100. Each of the plurality of elements 105 further includes a lock 180 that protects the contents of the object itself. Before a process, e.g., a thread, may attempt to read or modify the contents of the linked list 100, the process must acquire the list lock 110. Multiple threads may read the list concurrently, but only one may modify the list at any one time.
Modifications of a linked list are of one of three types: add an element to the list, move an element in the list, or remove an element from the list. To add an element to the list, the element is created and its pointers 140 and 150 are set to point to the addresses of the elements of the linked list that are to be immediately before and after the new element. In addition, the pointers 140 and 150 of the elements before and after the new element must be modified to point to the new element.
To move an element in the list, the pointers of the element that is to be moved are modified to point to different elements in the list. The elements that were before and after the moved element are modified to point to each other and the elements that are now before and after the moved element are modified to point to the moved element.
To remove an element from the list, the element's pointers are modified to no longer point to an element in the list and the pointers of the elements before and after the element that is being removed are modified to point to each other.
In order to make the necessary modifications to the elements of the linked list to add, move, or remove these elements, the lock 180 on the element must first be obtained. Thus, in order to perform work, e.g., adding a new element, moving an element, removing and element, or modifying the element itself, the list lock 110 must be obtained and the lock on the element 180 must be acquired.
There have been a number of mechanisms devised for performing work on doubly linked lists. In one mechanism a single thread takes the list lock and walks the list, i.e. sequentially obtains the lock for each element of the list for which work is required, performing the necessary work on each element of the list. This approach to performing work on a doubly linked list does not scale and creates a bottleneck for processing involving doubly linked lists.
A second approach to performing work on a doubly linked list is to have multiple threads in which one is designated the “producer” thread and the remaining threads are the “consumer” threads. The producer thread holds the list lock through the work operations. As each consumer thread finishes work, it requests more work from the producer thread. The producer thread provides the requesting consumer thread with the address of the next element in the linked list, or instructs the consumer thread to terminate. Once all work is done, the consumer threads die off by being instructed to terminate by the producer thread. Once all of the consumer threads have died off, the producer thread releases the list lock. This mechanism may result in consumer threads queuing up on the producer thread and thereby slowing down the processing of the linked list.
In another mechanism for performing work on a linked list, a hash table is associated with the list. The hash buckets may be divided up amongst the threads performing work on the linked list, i.e. the worker threads. The worker threads, having been given the hash value range to work on, acquire list locks for each hash bucket in turn and do work on the contents of the linked list. This mechanism can result in an uneven distribution of work if the hash function is imperfect, as hash functions frequently are.
In view of the problems with the known mechanisms for performing work on a doubly linked list, it would be beneficial to have an apparatus and method for distributing work on a doubly linked list amongst a plurality of worker threads that does not require additional locks or data structures to be created and which scales up with processor performance. In addition, it would be beneficial to have an apparatus and method that distributes work evenly amongst the worker threads without the need for any kind of hashing or arbitration system.